\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{boaz}[2003/03/20 Boaz's Style file]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Package boaz - macros for papers in LaTeX.
%
%Options:
%full/proceed - full or proceedings version - set full variable
%hylinks/nohylinks - use/don't use hyperlinks
%draft/final - working draft (show author notes) or final version
%titlepage/notitlepage - use/don't use a title page
%
%Options for Table of Contents, List of Figures, List of Tables:
%usetoc/nousetoc , uselot/nouselot , uselof/nouselof
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Important macros:
%DOCheader environment - put there abstract etc.
%\DOCkeywords command  - put keywords in title page
%
%\authnote - use to define author notes, as in:
%\newcommand{\Bnote}[1]{{\authnote{Boaz}{#1}}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\RequirePackage{times}
\RequirePackage{fullpage,amsfonts,latexsym,graphicx,amssymb}
\RequirePackage{amsmath,amsthm,amstext,url}
\RequirePackage{bm}
\RequirePackage{txfonts, pxfonts}


%%%%%%%%%%%%%%%%%%%%
% General switches




\def\full{1}
\def\hylinks{1}
\def\draft{1}
\def\usetitlepage{0}

\def\usetoc{1}
\def\uselot{0}
\def\uselof{0}

\DeclareOption{usetoc}{\def\usetoc{1}}
\DeclareOption{nousetoc}{\def\usetoc{0}}
\DeclareOption{uselot}{\def\uselot{1}}
\DeclareOption{nouselot}{\def\uselot{0}}
\DeclareOption{uselof}{\def\uselof{1}}
\DeclareOption{nouselof}{\def\uselof{0}}

\DeclareOption{full}{\def\full{1}}  % Full or proceedings version
\DeclareOption{proceed}{\def\full{0}}

\DeclareOption{hylinks}{\def\hylinks{1}} % 1  for links in pdf (hyperref package)
\DeclareOption{nohylinks}{\def\hylinks{0}}

\DeclareOption{draft}{\def\draft{1}} % 1 for working draft
\DeclareOption{final}{\def\draft{0}}

\DeclareOption{titlepage}{\def\usetitlepage{1}}  % 1 - use a separate page for title
\DeclareOption{notitlepage}{\def\usetitlepage{0}}



\ProcessOptions


\newif\ifpdf
\ifx\pdfoutput\undefined
\else
  \ifx\pdfoutput\relax
  \else
    \ifcase\pdfoutput
    \else
      \pdftrue
    \fi
  \fi
\fi

\ifnum\draft=1 % show authors' note if draft
    \def\ShowAuthNotes{1}
\else
    \def\ShowAuthNotes{0}
\fi

%%%%%%%%%%%%%%%%%%%%%%
% set up pdfLaTeX
%\ifpdf
% \ifnum\hylinks=0
% \pdfpagewidth=\paperwidth
% \pdfpageheight=\paperheight
% \fi
%\fi

%%%%%%%%%%%%%%%%%%%%%%
% Spacing

% positive
\newcommand{\sspace}{1ex}
\newcommand{\bspace}{1.5ex}

% negative
\ifnum\full=1
  \def\nnspace{}
\else
  \def\nnspace{\vspace{-1.5ex}}
\fi
\newcommand{\newitem}{\nnspace\item}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems & Definitions


\newtheorem{theorem}{Theorem}[section]

\newtheorem{claim}[theorem]{Claim}
\newtheorem{subclaim}{Claim}[theorem]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{example}[theorem]{Example}
\newtheorem{algorithm1}[theorem]{Algorithm}
\newtheorem{protocol}[theorem]{Protocol}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{assumption}[theorem]{Assumption}

\newenvironment{algorithm}[1][]{\begin{algorithm1}[#1]~\\
    \vspace{-0.2cm}}{\end{algorithm1}}

%\newcommand{\qed}{\begin{flushright}
%\rule{.1in}{.1in} \end{flushright}  }


%\newenvironment{proofsk}{\nopagebreak
%\noindent{\bf Proof Sketch:}}{ \qed \par \medskip}

\newcommand{\protocolPlacement}{htbp}


\newcommand{\BBBtmp}{}


\newcommand{\BBtmp}{}



\newcounter{BBtmpC}


\newenvironment{protocolf}[1]{\renewcommand{\BBtmp}{#1} \stepcounter{BBtmpC}
\renewcommand{\BBBtmp}{l\arabic{BBtmpC}}
 \begin{figure}[\protocolPlacement]}
{\begin{protocol} \label{BBtmpL:\BBBtmp}
\BBtmp
\end{protocol}
\addcontentsline{lot}{table}{\ifnum\hylinks=1%
Protocol~\ref*{BBtmpL:\BBBtmp}:\else
Protocol~\ref{BBtmpL:\BBBtmp}:
\fi \BBtmp} %\nnspace\nnspace \nnspace
 \end{figure}
}

\newenvironment{protocolf1}[1]{\renewcommand{\BBtmp}{#1} \stepcounter{BBtmpC}
\renewcommand{\BBBtmp}{l\arabic{BBtmpC}}
\begin{figure}[\protocolPlacement]}
{\begin{protocol} \label{BBtmpL:\BBBtmp} \BBtmp
\end{protocol}
\addcontentsline{lot}{table}{Protocol~\ref{BBtmpL:\BBBtmp}:
\BBtmp}
\nnspace\nnspace \nnspace
 \end{figure}  }

\newcommand{\protstepwidth}{11.5cm}
\newcommand{\plainprotStep}[2]{%
\begin{minipage}{\protstepwidth}
\vspace{0.5ex}
\begin{description} %\vspace{-1ex}
\newitem[#1]  #2 \nnspace \end{description}\nnspace \nnspace \end{minipage}}
\newcommand{\protStep}[3]{\plainprotStep{#2 (#1):}{#3}}

\newenvironment{algorithmf}[1]{\renewcommand{\BBtmp}{#1} \stepcounter{BBtmpC}
\renewcommand{\BBBtmp}{l\arabic{BBtmpC}}
 \begin{figure}[\protocolPlacement]}
{\begin{algorithm1} \label{BBtmpL:\BBBtmp}
\BBtmp
\end{algorithm1}
\addcontentsline{lot}{table}{Algorithm~\ref{BBtmpL:\BBBtmp}:
\BBtmp} %\nnspace\nnspace \nnspace
 \end{figure}

}

\newcommand{\inp}[1]{\underset{\downarrow}{#1}}
\newcommand{\outp}[1]{\overset{\downarrow}{#1}}


\newcommand{\subprotlength}{3cm}
\newcommand{\subprot}[7]{%
\begin{minipage}{\subprotlength}\begin{center}
\begin{tabular}{lcr}
$#2$ & $#3$ & $#4$ \\
\multicolumn{3}{c}{$#1$}\\
$#5$ & $#6$ & $#7$
\end{tabular}\end{center}
\end{minipage}}

\newcommand{\rightstep}[1]{%
$\underrightarrow{\quad #1 \quad}$ }

\newcommand{\leftstep}[1]{%
$\underleftarrow{\quad #1 \quad}$ }


\newcommand{\parties}[5]{%
\begin{minipage}{\subprotlength}\begin{center}
\begin{tabular}{lcr}
$#3$ & $#4$ & $#5$ \\
%\cline{1-3}
%\vline \hfill $#1$ &      & $#2$ \hfill \vline \\
$\boxed{#1}$ &      & $\boxed{#2}$ \\
%\cline{1-3}
\end{tabular}\end{center}
\end{minipage}}

\newenvironment{proofsk}{\begin{proof}[Proof Sketch:]}
{\end{proof}}


\newenvironment{smallproof}{\nopagebreak \begin{quote} %
\begin{small} \noindent{\bf Proof:}}{ \qed \par %
\end{small} \end{quote} \medskip}

\newenvironment{note}{\nopagebreak \begin{quote} %
\noindent{\bf Note:}}{%
\end{quote} \medskip}

\newenvironment{notes}{\nopagebreak \begin{quote} %
\noindent{\bf Notes:} \par%
\begin{itemize}}{%
\end{itemize}\end{quote} \medskip}






\newcommand{\APPENDIX}{%
 \appendix
 \ifnum\hylinks=1 \phantomsection \fi
 \addcontentsline{toc}{section}{Appendices}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author's notes

\ifnum\ShowAuthNotes=1
\newcommand{\authnote}[2]{{ \bf [#1's Note: #2]}}
\else
\newcommand{\authnote}[2]{}
\fi
\newcommand{\Bnote}[1]{{\authnote{Boaz}{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Complexity classes

\renewcommand{\P}{\mathbf{P}}
\newcommand{\NP}{\mathbf{NP}}
\newcommand{\PSPACE}{\mathbf{PSPACE}}
\newcommand{\NC}{\mathbf{NC}}
\newcommand{\Ppoly}{\mathbf{P}/poly}
\newcommand{\NEXP}{\mathbf{NEXP}}
\newcommand{\EXP}{\mathbf{EXP}}
\newcommand{\PCP}{\mathbf{PCP}}
\newcommand{\Ntime}{\mathbf{Ntime}}
\newcommand{\Dtime}{\mathbf{Dtime}}
\newcommand{\BPP}{\mathbf{BPP}}
\newcommand{\PromiseBPP}{\mathbf{PromiseBPP}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% refs macros - needed to use links in pdf

% \newif\ifpdf
% \ifx\pdfoutput\undefined
%   \pdffalse % we are not running PDFLaTeX
% \else
%   \pdfoutput=1 % we are running PDFLaTeX
%   \pdftrue
% \fi



% Set up PDF specific
%\ifpdf


\ifnum\hylinks=1

%%%%%
% For print, we might want to use
% colorlinks
% citecolor = black
% filecolor = black
% linkcolor = black
% urlcolor  = black
%
% Also possible to use plainpages=false
% to eliminate warnings of duplicate links

\ifpdf
\RequirePackage[pdftex,colorlinks,linkcolor=blue,filecolor = blue, citecolor = blue, urlcolor  = blue]{hyperref}
\else
\RequirePackage[colorlinks,linkcolor=blue,filecolor = blue, citecolor = blue, urlcolor  = blue]{hyperref}
\fi
\fi

\ifnum\hylinks=1
\newcommand{\namedref}[2]{\hyperref[#2]{#1~\ref*{#2}}}
\else
\newcommand{\namedref}[2]{#1~\ref{#2}}
\fi



%\newcommand{\sectionref}[1]{\hyperref[#1]{Section~\ref*{#1}}}
%\newcommand{\appendixref}[1]{\hyperref[#1]{Appendix~\ref*{#1}}}
%\newcommand{\theoremref}[1]{\hyperref[#1]{Theorem~\ref*{#1}}}
%\newcommand{\remarkref}[1]{\hyperref[#1]{Remark~\ref*{#1}}}
%\newcommand{\definitionref}[1]{\hyperref[#1]{Definition~\ref*{#1}}}
%\newcommand{\figureref}[1]{\hyperref[#1]{Figure~\ref*{#1}}}
%\newcommand{\lemmaref}[1]{\hyperref[#1]{Lemma~\ref*{#1}}}
%\newcommand{\claimref}[1]{\hyperref[#1]{Claim~\ref*{#1}}}
%\newcommand{\constructionref}[1]{\hyperref[#1]{Construction~\ref*{#1}}}
%\newcommand{\itemref}[1]{\hyperref[#1]{Item~\ref*{#1}}}
%\newcommand{\propertyref}[1]{\hyperref[#1]{Property~\ref*{#1}}}
%\newcommand{\protocolref}[1]{\hyperref[#1]{Protocol~\ref*{#1}}}
%\newcommand{\algorithmref}[1]{\hyperref[#1]{Algorithm~\ref*{#1}}}




\newcommand{\sectionref}[1]{\namedref{Section}{#1}}
\newcommand{\appendixref}[1]{\namedref{Appendix}{#1}}
\newcommand{\theoremref}[1]{\namedref{Theorem}{#1}}
\newcommand{\remarkref}[1]{\namedref{Remark}{#1}}
\newcommand{\definitionref}[1]{\namedref{Definition}{#1}}
\newcommand{\figureref}[1]{\namedref{Figure}{#1}}
\newcommand{\lemmaref}[1]{\namedref{Lemma}{#1}}
\newcommand{\claimref}[1]{\namedref{Claim}{#1}}
\newcommand{\constructionref}[1]{\namedref{Construction}{#1}}
\newcommand{\itemref}[1]{\namedref{Item}{#1}}
\newcommand{\propertyref}[1]{\namedref{Property}{#1}}
\newcommand{\protocolref}[1]{\namedref{Protocol}{#1}}
\newcommand{\algorithmref}[1]{\namedref{Algorithm}{#1}}
\newcommand{\assumptionref}[1]{\namedref{Assumption}{#1}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\DOCkeywords}[1]{\ifnum\usetitlepage=1 \vfill \paragraph{Keywords:} #1 \fi}

\newenvironment{DOCheader}{%
\ifnum\usetitlepage=1
\begin{titlepage}
 \thispagestyle{empty}
\fi
\maketitle
\ifnum\draft=1
\begin{center}\begin{Large}\textsc{Working Draft}\end{Large}\end{center}
\vspace{0.2cm}
\fi
} %%%% END
{
\ifnum\usetitlepage=1
\end{titlepage}
\fi
\ifnum\usetoc=1
%\newpage
\ifnum\hylinks=1 \ifpdf \pdfbookmark[1]{Table of contents}{tabOfCont}
\fi \fi
\tableofcontents
\fi

\ifnum\uselof=1
\listoffigures
\fi
\ifnum\uselot=1
\listoftables
\fi
\newpage
}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AtBeginDocument{
%\ifnum\draft=1
%\pagestyle{myheadings}
%\markright{\textsc{Draft}}
%\fi

}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\AtEndDocument{
\ifnum\usetitlepage=0

%\ifnum\usetoc=1
%\newpage
%\ifnum\hylinks=1 \ifpdf \pdfbookmark{Table of contents}{tabOfCont}
%\fi \fi
%\tableofcontents
%\fi

\ifnum\uselof=1
\listoffigures
\fi
\ifnum\uselot=1
\listoftables
\fi

\fi
}

%
% Macro added by Jiajin Yu
%


%
% mathify-- ensure argument is in math mode
%

\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General Macros


\newcommand{\eqdef}{\coloneqq}       % ``equals by definition''
% \newcommand{\eqdef}{\stackrel{\text{\tiny def}}{=}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\inr}{\in_{\mbox{\tiny R}}}
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\into}{\rightarrow}

\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\renewcommand{\vec}[1]{{\bm{#1}}}
\newcommand{\e}{\epsilon}
\newcommand{\ee}{\varepsilon}
\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}
\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\Com}{{\sf Com}}
\newcommand{\desc}{{\sf desc}}

%
% Useful symbols
%


\newcommand{\ihat}{\hat{\imath}}
\newcommand{\jhat}{\hat{\jmath}}
\newcommand{\Bool}{\it Bool}                   % booleans
\newcommand{\true}{\tt t}
\newcommand{\false}{\tt f}
\newcommand{\I}{\cal I}                         % interpretations
\newcommand{\M}{\cal M}                         % meaning functions
\newcommand{\A}{\cal A}                         % arithmetic interpretation
\newcommand{\B}{\cal B}                         % binary word interpretation
\newcommand{\TIME}{\mathop{\rm TIME}\nolimits}
\newcommand{\NTIME}{\mathop{\rm NTIME}\nolimits}
\newcommand{\SPACE}{\mathop{\rm SPACE}\nolimits}
\newcommand{\NSPACE}{\mathop{\rm NSPACE}\nolimits}
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
%\newcommand{\implies}{\Rightarrow}


%
% Useful functions
%

\newcommand{\abs}[1]{\mathify{\left| #1 \right|}}
\newcommand{\car}[1]{\mathify{\left| #1 \right|}}
\renewcommand{\Pr}[1]{\mathify{\mbox{Pr}\left[#1\right]}}
\newcommand{\Exp}[1]{\mathify{\mbox{Exp}\left[#1\right]}}
\newcommand{\set}[1]{\mathify{\left\{ #1 \right\}}}
\newcommand{\cset}[2]{\set{#1\\{}\mid\\{}#2}}  % a conditional notation to define sets
\newcommand{\lset}[2]{\set{#1,\ldots,#2}} % set {from,...,to}
\newcommand{\suchthat}{\vert}
\newcommand{\st}{\suchthat}

%
% abbreviations
%
\newcommand{\ie}{\emph{i.e.}}
\newcommand{\etc}{\emph{etc.}}
\newcommand{\eg}{\emph{e.g.}}
%\newcommand{\wlog}{\em w.l.o.g.}
\newcommand{\cf}{\em cf.}
\newcommand{\viz}{\em viz.}
\newcommand{\etal}{\emph{et al.}}
